МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ Курсова робота з дисципліни: “ Паралельні та розподілені обчислення” на тему: «Паралельне виконання операцій множення матриць» Завдання Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) : n1=5Б , n2=3П, n3=2І – КІ-44 де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно. ПІБ: Новосад Олег Євгенович; Група: КІ – 44: n1=5Б – Н = 230 n2=3П – В = 56 n3=2І – Л = 325 Отже маємо матрицю А(230*56) та матрицю В(56*325) Розробити та описати алгоритм множення матриць А*В на структурі, яка задається виразом: 3b – 6b – 2b – 5b – 10b – 13b – 14b – 11b де «nb»- номер букви П.І.Б студента. Новосад Олег Євгенович КІ-44: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  Н О В О С А Д О Л Е Г Є В Г Е Н О В И Ч   3 1  4 2    5 8  6 7        Отримаємо – ВАОСЕВГГ ( ВАОСЕГГГ ( ВАОСЕНГГ ( ВАОСЕНГЄ Для ВАОСЕНГЄ отримаємо наступні значення, які записуємо у стовпець і переводимо у двійкове 8-ми розрядне число, а в отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0. В = 20310 = 110010112 11001011 01001011 А = 2710 = 000110112 00011011 00011011 О = 25010 = 111110102 11111010 11011010 С = 8210 = 010100102 01010010 01000010 Е = 17110 = 101010112 10101011 => 10100011 Н = 13410 = 100001102 10000110 10000010 Г = 7410 = 010010102 01001010 01001100 Є = 3410 = 001000102 00100010 00100010 Згідно варіанту, 6 стовбець не містив в собі ‘1’, що заважало б коректному вирішенню поставленого завдання. З викладачем було узгоджено, що в цьому стовбці на позиції 6 біта (відлік йде зверху) поставити ‘1’ (ця одиниця виділена жирним накресленням). Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує певну 8-ми процесорну систему (структуру) із направленими зв’язками між вершинами. 3. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами: 3.1. Тип початкового завантаження даних type: Номер залікової книжки: 0809083 type = (0+8+0+9+0+8+3) = 28 mod 3 + 1 = 2 (через один процесор) 3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW: tU – час виконання однієї операції множення; tS  - час виконання однієї операції сумування; tP - час виконання однієї операції пересилання даних між процесорами; tZ - час виконання операції завантаження одних даних; tW - час виконання операції вивантаження одних даних. tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки. K = 7 tU=(9 +1)tS=(0 +1)tP=(8 +1)tZ=(3+1)tW tU=4tW tS=10/tw tP=1/tw tZ=9/tw Анотація Дана курсова робота полягає в розробці алгоритму перемноження матриць на 8 процесорах, при чому доступ до даних в пам’яті здійснюється один процесор. В курсовій наведена граф-схема виконання алгоритму множення двох матриць на кільцевій структурі, граф-схема зв’язків, графи пересилань даних, програмна реалізація алгоритму і проведені розрахунки часу виконання та ефективності. Програмна реалізація курсової роботи виконана у середовищі Microsoft Visual Studio 2010 на мові С з використанням бібліотек MPI (Message Passing Interface) і має консольний інтерфейс. Annotation The matrix multiplication algorithm for 8 processors was developed in this course work. The accesses to the data in the memory may take place through the one processor. In the exchange rate is shown graph-scheme of the algorithm for multiplying two matrices in a ring structure, the graph-scheme of re...